package com.example.demo.sort;

import cn.hutool.log.Log;

import java.util.Arrays;
import java.util.function.Function;
import java.util.function.Supplier;

/**
 * <pre>
 *  描述: 排序算法模板
 * </pre>
 *
 * @author godelgnis(wujiaer)
 * @version 1.0.0
 * @date 2022/1/7 9:53
 */
public abstract class SortAlgorithmTemplate {

    private static Log log = Log.get();

    private static int[] array = { 13, 17, 4, 2, 8, 12, 12, 13, 19, 18, 5, 9, 13, 0, 4, 17, 18, 18, 18, 5, 19, 19, 12, 4, 5, 3, 9, 8, 12, 10 };

    private static int[] answer = { 0, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 9, 9, 10, 12, 12, 12, 12, 13, 13, 13, 17, 17, 18, 18, 18, 18, 19, 19, 19 };

    public void run() {
        calculate(()->new SortAlgorithmWrapper(SortType.BUBBLE, this::bubbleSort));
        calculate(()->new SortAlgorithmWrapper(SortType.QUICK, this::quickSort));
        calculate(()->new SortAlgorithmWrapper(SortType.SIMPLE_INSERT, this::simpleInsertSort));
        calculate(()->new SortAlgorithmWrapper(SortType.SHELL, this::shellSort));
        calculate(()->new SortAlgorithmWrapper(SortType.SIMPLE_SELECT, this::simpleSelectSort));
        calculate(()->new SortAlgorithmWrapper(SortType.HEAP, this::heapSort));
        calculate(()->new SortAlgorithmWrapper(SortType.MERGE, this::mergeSort));
        calculate(()->new SortAlgorithmWrapper(SortType.MERGE_PLUS, this::mergeSortPlus));
        calculate(()->new SortAlgorithmWrapper(SortType.COUNT, this::countSort));
        calculate(()->new SortAlgorithmWrapper(SortType.BUCKET, this::bucketSort));
        calculate(()->new SortAlgorithmWrapper(SortType.RADIX, this::radixSort));
        calculate(()->new SortAlgorithmWrapper(SortType.JDK_SORT, this::jdkSort));
    }

    private void calculate(Supplier<SortAlgorithmWrapper> supplier) { calculate(supplier.get()); }

    private void calculate(SortAlgorithmWrapper wrapper) {
        calculate(wrapper, array, answer);
    }

    private void calculate(SortAlgorithmWrapper wrapper, int[] sourceArray, int[] answerArray) {
        log.info(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
        log.info("name: {}", wrapper.sortType.name());
        calculate(wrapper.function, sourceArray, answerArray);
        log.info("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<");
    }

    private void calculate(Function<int[], int[]> function, int[] sourceArray, int[] answerArray) {
        int[] clone = Arrays.copyOf(sourceArray, sourceArray.length);
        long s = System.nanoTime();
        int[] result = function.apply(clone);
        long e = System.nanoTime();
        boolean equals = result != null && Arrays.equals(result, answerArray);
        log.info("排序时间: {}ms, 排序结果: {}", (e - s)/1000000.00, equals);
    }

    /**
     * 冒泡排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] bubbleSort(int[] arr);
    /**
     * 快速排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] quickSort(int[] arr);
    /**
     * 简单插入排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] simpleInsertSort(int[] arr);
    /**
     * 希尔排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] shellSort(int[] arr);
    /**
     * 简单选择排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] simpleSelectSort(int[] arr);
    /**
     * 堆排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] heapSort(int[] arr);
    /**
     * 归并排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] mergeSort(int[] arr);
    /**
     * 增强归并排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] mergeSortPlus(int[] arr);
    /**
     * 计数排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] countSort(int[] arr);
    /**
     * 桶排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] bucketSort(int[] arr);
    /**
     * 基数排序
     * @param arr 待排序数组
     * @return 排好序的数组
     */
    protected abstract int[] radixSort(int[] arr);

    private int[] jdkSort(int[] arr) {
        Arrays.sort(arr);
        return arr;
    }

    private class SortAlgorithmWrapper {
        SortType sortType;
        Function<int[], int[]> function;

        SortAlgorithmWrapper(SortType typ, Function<int[], int[]> function) {
            this.sortType = typ;
            this.function = function;
        }
    }

    /**
     * 排序算法类型
     */
    private enum SortType {
        /**
         * 交换排序：冒泡排序、快速排序
         */
        BUBBLE, QUICK,
        /**
         * 选择排序：简单选择排序、堆排序
         */
        SIMPLE_SELECT, HEAP,
        /**
         * 插入排序：简单插入排序、希尔排序
         */
        SIMPLE_INSERT, SHELL,
        /**
         * 归并排序：归并排序、增强版归并排序
         */
        MERGE, MERGE_PLUS,
        /**
         * 非比较线性时间排序
         * 计数排序、桶排序、基数排序
         */
        COUNT, BUCKET, RADIX,
        /**
         * JDK自带排序算法
         */
        JDK_SORT
    }


    protected void swap(int[] arr, int i, int j) {
        int tmp =  arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
